A typical distributed computer system includes multiple interconnected nodes. Each node in the distributed computer system may include a separate processor. Accordingly, applications which execute in parallel on the distributed computer system are able to exploit the processing power provided by interconnection of the processors. For example, by combining the processing power provided by the multiple interconnected nodes, a given computation may be executed faster by partitioning the computation into multiple sections and executing each section in parallel on several nodes rather than executing the application serially on a single node.
Applications executing on several nodes may have synchronization barriers. A synchronization barrier synchronizes nodes by halting execution on the nodes that have reached a specified instruction until the remaining nodes have reached the specified instruction. For example, consider the scenario in which a dataset is divided into ten sections and each section is executed by a different node. Further, every fifty steps, each node communicates the results of the execution with the other nodes. Communicating the results may be performed using a send instruction and a corresponding receive instruction. The execution results are then used during the next fifty steps. When a node completes the execution of the fifty steps, the node executes the send instruction to send the result that the node calculates. The node further executes a receive instruction to receive the results from another node. The instruction to receive the execution results from other nodes forms a synchronization barrier. Thus, the execution of the application by the nodes is synchronized at the receive instruction.
Several reasons may exist for nodes to wait extended periods of time before the remaining nodes reach the synchronization barrier. One reason is because the execution of the application is often not the only operation being performed by the node. For example, an operating system on the node may perform management tasks for the node, such as input and output of data, scheduled maintenance tasks, etc. In such scenario, all the nodes in the distributed computer system are often forced to wait until the operating system completes the management tasks or until control is switched back to the application.
The delay may be increased when the same management task is performed by different nodes at different synchronization barriers. As an example, consider the scenario in which there are one thousand nodes, and each node has a one percent chance of performing a management task between any two synchronization barriers in the execution of the application. Thus, an average of ten of the nodes will perform a management task between each two synchronization barriers. Because all nodes must enter the barrier before any nodes leave the barrier, the nodes not performing the management task must wait for the ten nodes to complete the management task at each synchronization barrier. Therefore, the total delay due to the management task is increased. Specifically, rather than the delay being the sum of the amount of time to perform the management task on each node, the delay is the amount of time needed to perform the management task between each pair of barriers multiplied by the number of synchronization barriers.